class Solution {
public:
    int trap(vector<int>& height) {
        deque<pair<int, int>> que;
        int ans = 0;
        for (int i = 0; i < height.size(); i++)
        {
            int num = height[i];
            if (!que.empty() && que.front().first < height[i]) num = que.front().first;
            int temp = 1;
            while (!que.empty() && que.back().first <= height[i])
            {
                ans += que.back().second * (num - que.back().first);
                temp += que.back().second;
                que.pop_back();
            }
            que.push_back(pair<int, int>(height[i], temp));
        }
        return ans;
    }
};